The Internet is increasingly being used to conduct electronic business. Advertising is commonplace and many vendors use the Internet for the sale of products and services, including books and toys. Individuals use Internet-based online auction sites for selling a variety of goods that range from second hand books to rare collectible items.
The Internet has several advantages over the traditional media types. Firstly the reach of the Internet is much wider than any other traditional media type available. Thus, an item advertised for sale on the Internet is exposed to potentially more than a billion Internet users all over the world. Secondly, the Internet offers excellent search capabilities to users. State of the art search engines make it possible to type a few keywords and subsequently browse through a substantial amount of information present on the Internet that is related to these keywords. A user in search of a used car (e.g. a Honda Civic) may simply submit the phrase “for sale used Honda Civic” to a search engine to obtain a listing of used Honda Civic cars available for sale on the Internet. Thirdly, the Internet offers a relatively inexpensive way to communicate to users all over the world. Finally, the Internet connected with various public and private computer systems enables users to make use of software-based agents to perform many useful functions in an automated manner.
As a result, an increasing number of virtual electronic marketplaces are being setup on the Internet for the sale and purchase of goods and services. These marketplaces offer a variety of market mechanisms for negotiating contracts between buyers and sellers. The most common mechanisms currently used are fixed price sale, ascending price English auctions, descending price Dutch auctions, name-your-price and request-for-quotes.
In the fixed price sale mechanism, the seller publishes a fixed price for an item. Interested buyers may purchase the item by using an online payment method, such as a credit card or CyberCash, and by supplying a shipping address. In descending price Dutch auctions, sellers offer their items for sale beginning with a high initial price. A seller lowers the price of an item if buyers show no interest in the item. The price is lowered in a stepwise fashion until the seller finds a buyer for the item.
In ascending price English auctions, the sellers list items for sale on an online Internet-based auction site. Potential buyers peruse the item details and place bids on items of interest. The buyers may place additional bids in case of being outbid by other buyers. At close of the auction, the buyer with highest bid wins the item at the final bid price.
In the name-your-price mechanism, a seller supplies details of the item for which potential buyers can bid. After examining the details of the item, a buyer may make a bid for securing the item. If the bid amount is acceptable to the seller, a contract is concluded and the seller ships the item to the buyer after receiving the payment or payment information.
In the request-far-quotes mechanism, a buyer (typically a large corporate entity or a government body) interested in purchasing an item makes their intent public and calls on various parties to submit quotations for the item. Interested sellers submit offers for the sale of the item and the buyer selects the best offer.
The auction model used for FCC bandwidth auctions (www.fcc.gov) is called the multi-round simultaneous auction model. In this model, all the auctions start simultaneously and end simultaneously, when bidding on each of them stops. The model provides an opportunity to bid for more than one bandwidth license simultaneously, in order to enable a combination of licenses to be won by a bidder who values that combination the most.
Several other auction-like mechanisms having desirable properties have been proposed in research literature. Demange G. et al., in “Multi-item Auctions”, Journal of Political Economy, 1984, 94(4):863-872, describe a generalization of ascending English auctions to multiple heterogeneous auctions. In this mechanism, each item is auctioned independently as an ascending open-cry auction, but all the auctions open and close simultaneously. The bidders place bids on items that provide a maximum surplus. Demange et al. showed that this mechanism leads to a final allocation that can be made substantially close to the minimum competitive equilibrium price. Bertsekas D. P., in “Auction Algorithms for Network Flow Problems: A Tutorial Introduction”, Computational Optimization and Applications, 1992, 1:7-66, also discusses properties of this auction mechanism. Bansal V. and Garg. R., in “Efficiency and Price Discovery in Multi-item Auctions”, ACM SigEcom Exchanges, 2(1), Winter 2001, briefly discuss multi-item auctions.
Crawford V. P. and Knoer E., in “Job Matching with Heterogeneous Firms and Workers”, Econometrica, March 1981, 49(2):437-450, describe a mechanism in the context of firms and workers where workers are assigned to firms. A mechanism (called salary adjustment process) is described that converges to an equilibrium assignment and competitive prices (salaries). Kelso A. S. and Crawford V. P., in “Job Matching, Coalition Formation, and Gross Substitutes”, Econometrica, November 1982, 50(6):1483-1504, extend this mechanism to the case where the bidders have more general demand (called gross substitute). Gul F. and Stacchetti E., in “Walrasian Equilibrium with Gross Substitutes”, Journal of Economic Theory, July 1999, 87(1):95-124, and in “The English Auction with Differentiated Commodities,” Journal of Economic Theory, May 2000, 92(1):66-95, describe a similar auction procedure for generic bidder demands called gross substitutes.
Leonard H. B., in “Elicitation of Honest Preferences for the Assignment of Individuals to Positions”, Journal of Political Economy, 1983, 91:461-479, considers a sealed bid mechanism for allocating items to bidders. Vickery W., in “Counterspeculation, Auctions, and Competitive Sealed Tenders”, Journal of Finance, 1961, 16:8-37, describes a “second price” sealed bid auction mechanism for a single item.
Implementation of the above-described auction mechanisms in Internet-based marketplaces has been limited. However, more traditional and/or simpler mechanisms for selling items have been implemented in various marketplaces. U.S. Pat. No. 5,890,138, issued to Godin et al. on Mar. 30, 1999 and U.S. Pat. No. 5,835,896, issued to Fisher et al. on Nov. 10, 1998, each present a method of conducting online auctions, which enables users to participate using computers connected to the auction system via a computer or communications network.
Examples of online auction web sites on the World Wide Web (WWW) include www.auctions.yahoo.com, and www.ebay.com. The experimental auction server AuctionBot at the University of Michigan, Ann Arbor, USA, supports Vickrey auctions, (m+1)st-price auctions, mth-price auctions, continuous double auctions and chronological match auctions (e.g. http://auction.eecs.umich.edu) and is described by Wellman, P. R., Wellman M. P. and Walsh W. E. in “The Michigan Internet AuctionBot: A Configurable Auction Server for Human and Software Agents”, Proceedings of the 2nd International Conference on Autonomous Agents 1998, (Agents'98). Web sites such as www.amazon.com and www.walmart.com have implemented the fixed price sale mechanism. Web sites such as www.priceline.com have implemented the name your price mechanism for airline tickets and other travel related services. Some of these auction sites provide users with a capability to use very simple automated software-based agents, acting on behalf of those users, to place bids. Proxy bidding at the auction web site www.ebay.com is one such example.
In view of the foregoing, a need exists for the online implementation of multi-item generalization of auction mechanisms.